package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * 应该利用{@link Stack}来处理
 * @author yml
 *
 */
public class LeetCodeOffer31 {

	public static void main(String[] arg0) {
		int[] pushed = new int[] { 1, 2, 3, 4, 5 };
		int[] popped = new int[] { 4, 3, 5, 1, 2 };

		System.out.println("pushed的弹出序列可以是popped = "
				+ validateStackSequences(pushed, popped));
	}

	static int j = 0;

	public static boolean validateStackSequences(int[] pushed, int[] popped) {
		// 弹出序列，后一个数比前一个数后压入，一定可以出现
		// 所以只考虑后一个数比前一个数先压入的情况
		ArrayList<Integer> trackNums = new ArrayList<Integer>();
		for (int i = 0; i < pushed.length; i++) {
			System.out.print("pushed[" + i + "] = " + pushed[i]);
			System.out.println(", popped[" + j + "] = " + popped[j]);
			if (pushed[i] != popped[j]) {
				trackNums.add(pushed[i]);
			} else {
				j++;
				if (!isValidate(popped, trackNums)) {
					return false;
				}
			}
		}

		return true;
	}

	public static boolean isValidate(int[] popped, ArrayList<Integer> trackNums) {
		if (j >= popped.length) {
			return true;
		}
		System.out.println("trackNums = "
				+ Arrays.toString(trackNums.toArray()));
		System.out.println("popped[" + j + "] = " + popped[j]);
		if (trackNums.contains(popped[j])) {
			if (trackNums.get(trackNums.size() - 1) == popped[j]) {
				trackNums.remove(trackNums.size() - 1);
				j++;
				return isValidate(popped, trackNums);
			} else {
				return false;
			}
		} else {
			return true;
		}
	}

}
